CF487B Strip

一道并不难的 $dp$ 题。转移式很好列：

$dp[i]=min\{ dp[j]+1 \} ~~~~ (0 \le j \le i - l~\&\&max(j+1,i)-min(j+1,i)<=s)$

看到区间的最大值与最小值之差，我们很容易想到用 $st$ 表维护。这样可以$\Theta(n^2)$解决。

很显然的一个结论是，决策点是单调递增的。因为 $i$ 不断向右，区间的最值递增，决策点也必须向右调整。

并且，为了使答案更优，我们每次一定会选择最靠左的那个决策点。

所以，只需要维护最左边的决策点即可，转移复杂度$\Theta(n)$。

总时间复杂度$\Theta(nlogn+n)$

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f

const int MAXN = 100000 , MAXK = 20;
int n , l , s , a[ MAXN + 5 ] , f[ 2 ][ MAXN + 5 ][ MAXK + 5 ]; //0->max 1->min
int dp[ MAXN + 5 ];

void Init( ) {
    memset( f[ 1 ] , 0x3f , sizeof( f[ 1 ] ) );
    
    for( int i = 1 ; i <= n ; i ++ )
        f[ 0 ][ i ][ 0 ] = f[ 1 ][ i ][ 0 ] = a[ i ];
    for( int j = 1 ; ( 1 << j ) <= n ; j ++ )
        for( int i = 1 ; i + ( 1 << j ) - 1 <= n ; i ++ ) {
            f[ 0 ][ i ][ j ] = max( f[ 0 ][ i ][ j - 1 ] , f[ 0 ][ i + ( 1 << j - 1 ) ][ j - 1 ] );
            f[ 1 ][ i ][ j ] = min( f[ 1 ][ i ][ j - 1 ] , f[ 1 ][ i + ( 1 << j - 1 ) ][ j - 1 ] );
        }
}
int Query( int l , int r ) {
    int k = log2( r - l + 1 );
    return max( f[ 0 ][ l ][ k ] , f[ 0 ][ r - ( 1 << k ) + 1 ][ k ] ) - min( f[ 1 ][ l ][ k ] , f[ 1 ][ r - ( 1 << k ) + 1 ][ k ] );
}

int main( ) {
    scanf("%d %d %d",&n,&s,&l);
    for( int i = 1 ; i <= n ; i ++ ) 
        scanf("%d",&a[ i ]);
    Init( );

    memset( dp , 0x3f , sizeof( dp ) ); dp[ 0 ] = 0;
    int chk = 0;
    for( int i = l ; i <= n ; i ++ ) {
        while( ( i - chk >= l && ( Query( chk + 1 , i ) > s ) || dp[ chk ] == INF ) ) chk ++;
        if( i - chk >= l ) dp[ i ] = dp[ chk ] + 1;
    }
    printf("%d", dp[ n ] == INF ? -1 : dp[ n ] );
    return 0;
}